Recently, accompanying the development of information and communication technology and mobile computing technology, embedded systems, such as Personal Digital Assistants (PDAs), Hand-held Personal Computers (HPCs), mobile phones, e-books, and the like, have been developed. Embedded systems mainly use a flash memory as a storage medium.
In general, a flash memory has characteristics similar to Read Only Memory (ROM) and has different characteristics to hard disks. A flash memory is similar to ROM or a hard disk in that stored data is maintained even if power is turned off, since it is a nonvolatile memory, and is more reliable than a hard disk. A flash memory can operate with low power, and has an access time as quick as Random Access Memory (RAM). A flash memory is rewritable and is suitable for portable devices due to its small size.
However, a flash memory is much more expensive than a hard disk, and if a user wishes to write new data in a space occupied by an old data, an erasing the old data is necessary before the new data is written. There is a problem in that the time taken to perform the erasing is 100 times longer than a time to read a data.
Based on a 28F640J3A model flash memory developed by Intel Co., a time to read data is 100-150 nsec, which is similar to RAM, however, a time to write and erase data is relatively slow. A time to write data using a 32-byte buffer is around 218 μsec, and a data write time of an erase block unit is around 0.8 sec per block. In addition, the size of an erase block, in which all data can be erased at once is fixed to 128 Kbytes, and the number of times the erase block can be used at a normal temperature is fixed to around 100,000 times. The erase block indicates a space of a flash memory in which all data can be erased at once and is called a segment.
Conventional technologies for building a file system using a flash memory are disclosed in U.S. Pat. No. 5,404,485 entitled “Flash File System” and a paper, pages 155-164, entitled “A Flash Memory Based File System,” USENIX Technical Conference, 1995. In addition, Journaling Flash File System (JFFS) in which a log-structured file system is applied to a flash memory was disclosed in U.S. Pat. No. 6,128,630 entitled “Journal Space Release for Log-structured Storage Systems” and U.S. Pat. No. 5,530,850   entitled “Data Storage Library Array with Log-structured File System Which Allows Simultaneous Write and Garbage Collection”.
A log-structured file system allows a file system to be constituted in a hard disk, allows versions of previous data and newly updated data to be maintained in a log format using a method of sequentially storing generated data, and allows data in which a problem has occurred to be recovered by going back to previous data.
JFFS allows a file system to be constituted in a flash memory using a log-structured file system and allows generated data to be sequentially stored. JFFS was developed by Axis Communications in the United States, and JFFS2 corresponding to version 2 thereof was developed by RedHat in the United States based on GNU Public Licenses (GPL) of Free Software Foundation (FSF).
One important reason why a journaling method is used when a file system is constituted in a flash memory by JFFS is that the integrity of data can be guaranteed. According to a characteristic of embedded systems commonly using a flash memory, the possibility that the supply of power is suddenly cut off is very high. In general, when a computer system reads or writes data, for storage efficiency, the computer system uses a method of storing the data in a buffer, performing a predetermined operation related to the data, and storing the data in a storage medium without directly storing the data in the storage medium.
In this case, if power is suddenly turned off, intermediate data disappears, and it is difficult to detect a proceeding state of data remaining in the storage medium. In addition, most additional meta data for creating a storage structure or a file system is temporarily stored in RAM. If this meta data disappears, it is difficult to guarantee the integrity of data or the file system.
Thus, the journaling method is used, and if data is logged and stored using the journaling method, the integrity of data can be easily guaranteed, and the amount of metadata decreases, and thus the metadata can be easily managed.
However, the biggest problem of JFFS is that since all data is stored in the order it was generated, files of a file system and metadata for managing the files must be sequentially stored. According to JFFS, when a personal computer (PC) is turned on and a file system is mounted, since all metadata must be read and transferred to RAM, the entire space of a flash memory must be read, and thus a very long time is required for the mounting process.
As the capacity of a flash memory increases, the time required for the mounting process increases significantly, and thus a booting time taken to turn on and use an embedded system increases proportionally. Due to this, JFFS is not suitable for embedded systems to which quick access is required.
Besides the simplicity of storing and the integrity, another reason for sequentially storing data using the journaling method is that wear-leveling must be considered. A flash memory cannot be used indefinitely. Although the lifespan of a flash memory varies from product to product, a flash memory can be reused around 100,000 to 1,000,000 times.
Since this lifespan is applied to each segment that is an erase block unit, if a lifespan of a specific segment of a flash memory ends since an erase and write operation is concentrated in the specific segment, the flash memory cannot be used or the useless segment must be separately managed. In order to prevent this problem, wear-leveling, whereby an erase operation is evenly for all segments, must be achieved. Since the journaling method sequentially performs the erase operation, wear-leveling is naturally achieved.
However, a sequential erasing method to achieve the wear-leveling causes a decrease in the data input/output rate of the entire system. In a journaling storing method, a location of a store operation will be referred to as a “head”, and a location of an erase operation will be referred to as a “tail”. Before the store operation is performed from a first free space of a flash memory to the end and the head reaches the end of the flash memory, only if a segment indicated by the tail is erased in a state where there exist some free spaces, data can be continuously stored in the flash memory.
While the head is used to store data toward the end of the flash memory, useless data and newly updated data may exist. In this case, the useless data of the flash memory is not erased but represented in an invalid state. For the updated data, data before the updating is performed is represented in the invalid state, and the updated data is stored in a segment indicated by the head. By doing this, when a problem occurs, recovery is easily performed, and the integrity can be maintained. During this process, when a segment indicated by the tail must be erased, if all data in the segment is invalid, the segment can be immediately erased, but if valid data exists in the segment, the segment can be erased only after the valid data is moved to a segment indicated by the head. However, if almost all data in the segment indicated by the tail is valid, a long time is required to move the valid data to the segment indicated by the head. This phenomenon occurs since the erase operation is sequentially performed even if a segment in which most data is invalid exists in an intermediate portion of journaling.
A reason why a segment indicated by the tail is erased is because a storage space of the flash memory is insufficient, and if all of the segment indicated by the head is used to move the valid data, even if the segment of the tail part is erased, a storage space is still insufficient, and thus this process must be repeated. If such data is fixed data continuously remaining in a system, the above process must be performed every time journaling is performed. This significantly decreases the performance of the system.
In order to prevent the above problems, if valid data occupies most of a segment, the segment is skipped without being erased. However, if the segment is simply not erased, it violates the wear-leveling, and thus a compromising scheme must be found between the skipping and wear-leveling. In addition, users desire a fast booting time regardless of what internal storage medium is used, and conventional journaling storing methods cannot satisfy these requirements.